package cxydmmszl.chapter02.t030;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

/**
 * <li style="color: red;">Prob</li>
 * 合并两个有序的单链表
 * <li style="color: green;">Desc</li>
 * 给定两个升序的单链表的头节点 head1 和 head2，请合并两个升序链表，
 * 合并后的链表依然升序，并返回合并后链表的头节点。
 * <li style="color: green;">Input</li>
 * 两个升序的单链表的头节点 head1 和 head2
 * <li style="color: green;">Output</li>
 * 在给定的函数内返回新链表的头指针。
 * <li style="color: blue;">Link</li> CD159
 *
 * @author habitplus
 * @since 2021-09-10 22:19
 */
public class Main {
    private static final StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    private static int nextInt() {
        try {
            st.nextToken();
            return (int) st.nval;
        } catch (IOException e) {
            e.printStackTrace();
        }
        return 0;
    }

    private static class Node {
        int val;
        Node next;
        public Node(int val) {
            this.val = val;
        }
    }

    private static Node readAndGenList(int n) {
        Node tou = new Node(0), pre = tou, node;
        int num;
        for (int i = 0; i < n; i++) {
            num = nextInt();
            node = new Node(num);
            pre.next = node;
            pre = node;
        }

        return tou.next;
    }

    private static void printLinkedList(Node head) {
        StringBuilder sb = new StringBuilder();
        while (head != null) {
            sb.append(head.val).append(" ");
            head = head.next;
        }
        System.out.println(sb.toString());
    }

    private static Node merge(Node h1, Node h2) {
        if (h1 == null || h2 == null) {
            return h1 == null ? h2 : h1;
        }

        Node tou = new Node(0);
        tou.next = h1;
        Node pre = tou, nxt;

        // 将 h2 合并到 h1 上
        while (h1 != null && h2 != null) {
            if (h1.val > h2.val) {
                nxt = h2.next;
                pre.next = h2;
                h2.next = h1;
                pre = h2;
                h2 = nxt;
            } else {
                pre = h1;
                h1 = h1.next;
            }
        }

        pre.next = h1 == null ? h2 : h1;

        return tou.next;
    }

    public static void main(String[] args) {
        int n = nextInt();
        Node h1 = readAndGenList(n);

        int m = nextInt();
        Node h2 = readAndGenList(m);

        h1 = merge(h1, h2);

        printLinkedList(h1);
    }

}
